package code;


public class StockIII {
	
	public int maxProfit(int[] prices){
		int ans=0;
		int days=prices.length;
		int i,j,k;
		if(days<2)	return 0;
		
		int low=prices[0];
		int[] dp=new int[days];
		int[] redp=new int[days];
		
		if(days<2)	return 0;
		dp[0]=0;
		dp[days-1]=0;
		
		/*
		 * 正向求0~i这些天中，买卖一次获得的最大利润
		 */
		for(i=1;i<days;i++){
			dp[i]=0;
			if(low>prices[i]){
				low=prices[i];
			}
			if(dp[i]<prices[i]-low)
				dp[i]=prices[i]-low;
			if(dp[i]<dp[i-1])	
				dp[i]=dp[i-1];
		}
		/*
		 * 逆向求i~n些天中，买卖一次获得的最大利润
		 */
		int high=prices[days-1];
		for(i=days-2;i>=0;i--){
			if(high<prices[i]){
				high=prices[i];
			}
			if(redp[i]<high-prices[i])
				redp[i]=high-prices[i];
			if(redp[i]<redp[i+1])
				redp[i]=redp[i+1];
		}
		/*
		 * 最多两次买卖即可分割成0~i与i+1~n之和的最大值
		 */
		for(i=0;i<days;i++){
			if(i==0){
				if(ans<redp[i])
					ans=redp[i];
			}
			else if(i==days-1){
				if(ans<dp[i])
					ans=dp[i];
			}
			else{
				if(ans<dp[i-1]+redp[i])
					ans=dp[i-1]+redp[i];
			}
		}
//		for(i=0;i<days;i++){
//			System.out.println(i+"   "+dp[i]+"   "+redp[i]);
//		}
		return ans;
	}
	public static void main(String[] args){
		StockIII stock=new StockIII();
		int[] prices={2,1,2,0,1};
		int ans=stock.maxProfit(prices);
		System.out.println(ans);
	}
}
